package 字符串.单词查找树;

/**
 * @description:
 * @author: ywk
 * @date: 2021-09-05
 */
public class 三向单词查找树的符号表 {
    public static class TST<Value> {
        private Node root;

        private class Node {
            char c;
            Node left, mid, right;
            Value val;
        }

        public Value get(String key) {
            Node x = get(root, key, 0);
            if (x == null) {
                return null;
            }
            return x.val;
        }

        private Node get(Node x, String key, int d) {
            if (x == null) {
                return null;
            }
            char c = key.charAt(d);
            if (c < x.c) {
                return get(x.left, key, d);
            } else if (c > x.c) {
                return get(x.right, key, d);
            } else if (d < key.length() - 1) {
                return get(x.mid, key, d + 1);
            } else {
                return x;
            }
        }

        /**
         * 最长前缀
         */
        public String longestPrefixOf(String s) {
            int length = search(root, s, 0, 0);
            return s.substring(0, length);
        }

        private int search(Node x, String s, int d, int length) {
            if (x == null) {
                return length;
            }
            if (x.val != null) {
                length = d;
            }
            if (d == s.length()) {
                return length;
            }
            char c = s.charAt(d);
            if (c < x.c) {
                return search(x.left, s, d, length);
            } else if (c > x.c) {
                return search(x.right, s, d, length);
            } else {
                return search(x.mid, s, d + 1, length+1);
            }
        }
        public void put(String key, Value val) {
            root = put(root, key, val, 0);
        }

        private Node put(Node x, String key, Value val, int d) {
            char c = key.charAt(d);
            if (x == null) {
                x = new Node();
                x.c = c;
            }
            if (c < x.c) {
                x.left = put(x.left, key, val, d);
            } else if (c > x.c) {
                x.right = put(x.right, key, val, d);
            } else if (d < key.length() - 1) {
                x.mid = put(x.mid, key, val, d + 1);
            } else {
                x.val = val;
            }
            return x;
        }
    }
}